package main

type ListNode struct {
	Val  int
	Next *ListNode
}

func insertionSortList(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}
	hair := &ListNode{Val: 0, Next: head}
	n := head
	for n.Next != nil {
		next := n.Next
		val := next.Val
		n1 := hair
		for n1 != n {
			// hair < any
			if (n1.Val < val && val <= n1.Next.Val) || (n1 == hair && val <= n1.Next.Val) {
				// insert
				n.Next = next.Next
				next.Next = n1.Next
				n1.Next = next
				break
			} else {
				n1 = n1.Next
			}
		}
		if n == n1 {
			n = next
		}
	}
	return hair.Next
}

func main() {
	n1 := &ListNode{Val: -2147483647}
	n2 := &ListNode{Val: -2147483648}

	n1.Next = n2
	r := insertionSortList(n1)
	println(r)
}
